/*
 * @lc app=leetcode.cn id=821 lang=cpp
 *
 * [821] 字符的最短距离
 */

// @lc code=start
class Solution
{
public:
    vector<int> shortestToChar(string s, char c)
    {
        int n = s.size();
        deque<int> q;
        vector<int> ans(n, -1);
        // 将 c 字符位置当作BFS起点，并将其结果置为 0
        for (int i = 0; i < n; i++)
        {
            if (s[i] == c)
            {
                ans[i] = 0;
                q.push_back(i);
            }
        }

        int dir[2] = {1, -1};
        while (!q.empty())
        {
            int curr = q.front();
            q.pop_front();
            for (auto x : dir)
            {
                int next = curr + x;
                if (next < 0 || next >= n || ans[next] != -1)
                {
                    continue;
                }
                ans[next] = ans[curr] + 1;
                q.push_back(next);
            }
        }

        return ans;
    }
};
// @lc code=end
